package leetcode.slidingwindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//438. 找到字符串中所有字母异位词
public class FindAnagrams {
    public static void main(String[] args) {
        String s = "abab";
        String p = "ab";
        System.out.println(findAnagramsP(s, p));
//        int[] s1={1,23,3};
//        int[] s2={1,23,3};
//        System.out.println(Arrays.equals(s1,s2));
    }

    //通用滑动窗口----错误
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int m = s.length();
        int count = p.length();
        int[] need = new int[128];
        for (int i = 0; i < p.length(); i++) {
            need[p.charAt(i)]++;
        }
        int left = 0, right = 0, size = Integer.MAX_VALUE;
        while (right < m) {
            char ch = s.charAt(right);
            if (need[ch] > 0) {
                count--;
            }
            //如果不是要找的字符，将会被减成负数
            need[ch]--;
            if (count == 0) {
                //缩小
                while (need[s.charAt(left)] < 0 && left < right) {
                    need[s.charAt(left)]++;
                    left++;
                }
                if (right - left + 1 < size) {
                    size = right - left + 1;
                }
                if (size == p.length()) {
                    res.add(left);
                }
                //扩大
                need[s.charAt(left)]++;
                count++;
                left++;
            }

            right++;
        }

        return res;
    }


    //官方
    public static List<Integer> findAnagrams2(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<Integer> res = new ArrayList<>();
        if (m < n) {
            return res;
        }
        int[] cntP = new int[26];
        int[] cntS = new int[26];
        for (int i = 0; i < n; i++) {
            cntP[p.charAt(i) - 'a']++;
            cntS[s.charAt(i) - 'a']++;
        }
        System.out.println(Arrays.toString(cntP));
        System.out.println(Arrays.toString(cntS));
        if (Arrays.equals(cntS, cntP)) {
            res.add(0);
        }
        for (int i = n; i < m; i++) {
            cntS[s.charAt(i) - 'a']++;
            cntS[s.charAt(i - n) - 'a']--;
            if (Arrays.equals(cntS, cntP)) {
                res.add(i - n + 1);
            }
        }
        return res;
    }

    // 滑动窗口
    public static List<Integer> findAnagramsP(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] c1 = new int[26];
        int[] c2 = new int[26];
        int m = s.length();
        int n = p.length();
        // 词频统计字符串p
        for (int i = 0; i < n; i++) {
            c2[p.charAt(i) - 'a']++;
        }
        // 统计滑动窗口内s的子串词频
        int index = 0;
        for (int i = 0; i < m; i++) {
            c1[s.charAt(i) - 'a']++;
            // 控制滑动窗口大小,保证窗口内只有字符串p长度的内容，如果比其大，就滑动窗口
            if (i - index + 1 > n) {
                c1[s.charAt(index++) - 'a']--;
            }
            if (Arrays.equals(c1, c2)) {
                res.add(index);
            }
        }
        return res;
    }


}
